package 代码随想录_动态规划.基础题目;

/**
 * @author zx
 * @create 2022-05-22 12:33
 * 1.确定dp数组（dp table）以及下标的含义
 * dp[i]的定义为：第i个数的斐波那契数值是dp[i]
 * 2.确定递推公式
 * 状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];
 * 3.dp数组如何初始化
 * dp[0] = 0;
 * dp[1] = 1;
 * 4.确定遍历顺序
 * dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
 * 5.举例推导dp数组
 * 按照递推公式dp[i] = dp[i - 1] + dp[i - 2]，推导一下：
 * 当N为10的时候，dp数组应该是如下的数列：
 * 0 1 1 2 3 5 8 13 21 34 55
 *
 */
public class 斐波那契数_509 {
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
            System.out.println(dp[i]);
        }
        return dp[n];
    }
}
